Transmitted units of data (e.g., cells, packets, frames) are typically “policed” upon their entrance to a network. Often, the transmitted units of data are associated with a particular connection or other parameter (e.g., source node or port identification, destination node or port information, combination of source/destination identification information, etc.) that can be traced to a particular rate of service that the network is designed to offer an entity (e.g., a user, another network, equipment, etc.) that sent the transmitted unit of data to the network. For example, in the case of a Frame Relay network, a connection with a particular rate of service (e.g., as measured in bytes/sec) may be established; and, the frames that are offered to the Frame Relay network for transport over the connection are expected to arrive to the Frame Relay network at a rate that is approximately “in compliance” with the rate of service of the connection.
To the extent that the entity that is sending the frames for the particular connection sends the frames to the network at a rate that is approximately the same as the service rate of the connection, the Frame Relay network is expected to allow the frames to be carried by the network over the connection. However, if frames begin to arrive at a rate that exceeds the service rate of the connection, the network is allowed to “drop” the frames (or carry them only on a best effort basis, etc.). That is, the network is designed to thwart service as the offered rate exceeds the rate that has been established for the connection. The activity of thwarting or not thwarting service based upon the offered rate is often referred to as “policing”, “input policing” and the like.
FIG. 1 shows a diagram 100 that describes a basic input policing algorithm. The particular diagram 100 of FIG. 1 describes an input policing scheme that is described in the International Telecommunications Union (ITU) I.370 standard “Congestion Management For The ISDN Frame Relaying Bearer Service”. According to the approach of FIG. 1, the amount of data that arrives for a discrete amount of time Tc (which may be referred to as “the window of time Tc”, “the time window”, “the window of time”, “the measurement window”, “the measurement time window”, “the measurement time window size”, “the measurement interval” and the like) is tracked. If the amount of data that arrives within the window of time is less than or equal to a committed burst (Bc), the data is allowed to be carried by the network. As such, the data rate cir=Bc/Tc corresponds to the committed data rate that is associated for the connection.
According to the approach of FIG. 1, if an excess burst (Be) amount of data beyond Bc arrives within the time window (such that the total amount of data to arrive within time window Tc is less than or equal to Bc+Be) the one or more frames that carry data beyond Bc are tagged as Discard Eligible (DE) (e.g., by activating a bit in a frame header). When a frame is marked as discard eligible it is effectively labeled as being not in compliance with the service rate of its particular connection. However, marking a packet as non conforming with respect to the service rate of its connection (rather than discarding it immediately) allows the network to grant some degree of forgiveness. For example, the packet may be handled on a “best effort basis” wherein, if any excess/unused bandwidth capacity is available to carry the frame, the frame will be allowed to be forwarded for transport through the network with the excess/unused bandwidth.
If an amount of data beyond Be+Bc arrives within the time window, the one or more frames that carry data beyond Be+Bc are discarded. Here, for frames that represent an offered rate in excess of Bc+Be within the time window, no forgiveness is provided. The Bc data quantity is often referred to as the “committed burst” (because the connection is committed to carrying a rate of cir=Bc/Tc); and, the Be data quantity is often referred to as the “excess burst” (because the connection will forgive, by marking as discard eligible rather than discarding, those frames that represent an excess offered rate of Be/Tc beyond Bc/Tc). A problem with prior art attempts to implement the above described algorithm is their failure to comply with its basic principles.
In particular, the algorithm described above should force a separate analysis for each recognized window of time Tc; but, as described in more detail below, the known prior art solution does not operate in this manner. FIG. 2a shows a depiction of the known prior art approach (referred to as a “leaky bucket” approach) that has previously been used to implement the I.370 policing policy. Here, a poling unit 200 is implemented with a queue that is serviced according to a pair of queue servicing rates. Over time, the first queue servicing rate will reveal itself to be approximately equal to the committed service rate of the connection (cir=Bc/Tc); and, over time, the second queue servicing rate will reveal itself to be approximately equal to the excess service rate permitted by the connection (Be/Tc=(Be/Bc)cir).
A problem with the known prior art approach, however, is that there is no “notion” of the time Tc. That is, the functional unit responsible for measuring traffic against the committed and excess service rates implements the policing policy at time intervals other than Tc (e.g., “T”). Here, when an analysis is made (e.g., T seconds after the last analysis was made), the functional unit re-evaluates the connection by calculating: 1) “how many” bytes of received information should be serviced according to the committed service rate (i.e. (Bc/Tc)T); and, 2) “how many” bytes of received information should be “marked as discard eligible” and serviced according to the excess service rate (i.e., (Be/Tc)T). A number of received bytes equal to (Bc/Tc)T are then allowed to continue downstream without being marked as discard eligible and; and (if available) a number of bytes equal to (Be/Tc)T are allowed to continue downstream marked as discard eligible. After this, any remaining bytes are discarded.
Here, although the proper service rates will be implemented over time, because the functional unit operates according to a periodic time T and not a periodic time Tc—the precise I.370 standard is not followed. The result is an effective “spilling over”, across Tc boundaries, of network resources devoted to the connection. FIG. 2b demonstrates the problem in more detail.
FIG. 2b shows a first burst of data 210 that arrives at time t1; and, a second burst of data 220 that arrives at time t2. For simplicity, both of data bursts 210, 220 comprise Bc+Be worth of data. Note that the phase alignment of FIG. 2b shows three synchronously spaced Tc time windows: a first that spans from t=0 to t=Tc; a second that spans from t=Tc to t=2Tc and a third that spans from t=2Tc to t=3Tc. Here, as both data bursts 210, 220 arrive in the same time window between t=Tc and t=2Tc, strict application of the I.370 standard would demand that the second data burst 220 be discarded.
However, because the known prior art method operates over a time period T (which can be assumed to be greater than Tc) both data bursts will be accepted if the subsequent Tc window (between 2Tc and 3Tc) does not receive any traffic and the next inquiry after a passing of time T arises after 3Tc. As discussed, however, strict compliance with the I.370 standard would cause the second data burst 220 to be discarded.